package com.jeff.learn.heap;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 堆测试
 * 堆是一种特殊的树结构，它可以用来实现优先队列（PriorityQueue）和堆排序（HeapSort）。
 * 堆是一个完全二叉树，并且每个节点的值都大于或等于其子节点的值。
 * 堆的应用：
 * 1. 优先队列：堆可以用作优先队列，可以实现O(1)的入队和出队操作，并且可以保证每次弹出的元素都是优先级最高的。
 * 2. 堆排序：堆排序是一种排序算法，它利用了堆的特性，可以将任意无序的序列变成有序序列。
 * 3. 堆的应用还包括很多，比如：
 *    - 堆排序算法：堆排序是一种基于堆的数据结构，可以用来对一组元素进行排序。
 *      堆排序的过程是：
 *      1. 创建一个最大堆（或最小堆）
 *      2. 将堆顶元素与最后一个元素交换，然后将堆的大小减一
 *      3. 重复步骤2，直到堆的大小为1
 *      4. 堆排序完成，得到的序列就是有序的。
 * 
 *
 * @author yaojianfeng
 */
public class HeapTest {

    public static class MinHeapComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer x, Integer y) {
            return x - y; // 从小到大排序
        }
    }
    public static class MaxHeapComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer x, Integer y) {
            return y - x; // 从大到小排序
        }
    }

    public static void main(String[] args) {
        // 创建自定义小顶堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(new MinHeapComparator());

        // 添加元素到自定义小顶堆
        minHeap.add(5);
        minHeap.add(3);
        minHeap.add(8);
        minHeap.add(1);
        minHeap.add(2);

        // 输出自定义小顶堆的元素（按照顺序）
        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " ");
        }

        System.out.println("=============================================");
        // 创建自定义大顶堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new MaxHeapComparator());

        // 添加元素到自定义小顶堆
        maxHeap.add(5);
        maxHeap.add(3);
        maxHeap.add(8);
        maxHeap.add(1);
        maxHeap.add(2);

        // 输出自定义小顶堆的元素（按照顺序）
        while (!maxHeap.isEmpty()) {
            System.out.print(maxHeap.poll() + " ");
        }
    }
}

